package C025;

import java.util.Arrays;

/**
 * ClassName: HeapSort
 * Package: C025
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/12/10 11:03
 * @Version 1.0
 * @Since 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int n = 10000;
        int size = 100;
        int length = 20;
        for (int i = 0; i < n; i++) {
            int[] arr1 = randomGenerateArr(size, length);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);
            int[] arr4 = Arrays.copyOf(arr1, arr1.length);
            heapSort(arr1);
            Arrays.sort(arr2);
            heapSort2(arr3);
            if(!Arrays.equals(arr1, arr2) || !Arrays.equals(arr3, arr1)) {
                System.out.println("error !!!");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println(Arrays.toString(arr3));
                System.out.println(Arrays.toString(arr4));
                return;
            }
        }

        System.out.println("success !!!");

    }

    public static int[] randomGenerateArr(int size, int length) {
        int[] ints = new int[length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = (int) (Math.random() * size);
        }
        return ints;
    }

    public static void heapSort2(int[] arr) {
        // 调整为大根堆
        // 从下至顶调整堆，时间复杂度为 O(N),向下调整，等比数列求和-计算时间复杂度
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        // 堆顶弹出，与最后一个元素交换，然后进行向下调整
        for (int size = arr.length - 1; size >= 0;size --) {
            swap(arr, 0, size);
            heapify(arr, 0, size);
        }
    }

    /**
     * 堆排序 - 从顶至下
     * @param arr
     */
    public static void heapSort(int[] arr) {
        // 调整为大根堆
        // 从顶至下调整堆，时间复杂度为 O(NlogN),向上调整
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i, i + 1);
        }

        // 堆顶弹出，与最后一个元素交换，然后进行向下调整
        for (int size = arr.length - 1; size >= 0;size --) {
            swap(arr, 0, size);
            heapify(arr, 0, size);
        }
    }

    /**
     * 向下调整，变小的时候
     * @param arr
     * @param index
     */
    public static void heapify(int[] arr, int index, int size) {
        if(index >= size) {
            return;
        }

        int l = index * 2 + 1;
        while (l < size) {
            int r = index * 2 + 2;
            int bestIndex = r >= size || arr[l] > arr[r] ? l : r;
            bestIndex = arr[bestIndex] > arr[index] ? bestIndex : index;
            if(bestIndex == index) {
                break;
            }
            swap(arr, index, bestIndex);
            index = bestIndex;
            l = bestIndex * 2 + 1;
        }
    }

    /**
     * 向上调整，变大的时候会使用
     * @param arr
     * @param index
     * @param size
     */
    public static void heapInsert(int[] arr, int index, int size) {
        if(index >= size) {
            return;
        }
        int parent = (index - 1) >> 1;
        while(parent >= 0) {
            if(arr[index] > arr[parent]) {
                swap(arr, index, parent);
            }
            index = parent;
            parent = (index - 1) >> 1;
        }
    }

    private static void swap(int[] arr, int index, int bestIndex) {
        int temp = arr[index];
        arr[index] = arr[bestIndex];
        arr[bestIndex] = temp;
    }


}
